// 版权归Go作者所有。版权所有。
// 此源代码的使用受BSD样式
// 许可证的约束，该许可证可以在许可证文件中找到。

// 待办事项：改为在区块开始时直播？

package ssa

import (
	"cmd/compile/internal/ir"
	"cmd/compile/internal/types"
	"cmd/internal/src"
	"fmt"
)

type stackAllocState struct {
	f *Func

	// live是stackalloc的输出。
	// live[b.id]=块b末尾的活动值。
	live [][]ID

	// stackAllocState的多个用户
	// 。
	values    []stackValState
	interfere [][]ID // interfere[v.id]=干扰v.
	names     []LocalSlot
	slots     []int
	used      []bool

	nArgSlot, // 源于arg插槽的值数
	nNotNeed, // 不需要堆栈插槽的值数
	nNamedSlot, // 使用命名堆栈插槽的值数
	nReuse, // 重用堆栈插槽的值数
	nAuto, // 为堆栈插槽分配的自动数。
	nSelfInterfere int32 // 自干扰次数
}

func newStackAllocState(f *Func) *stackAllocState {
	s := f.Cache.stackAllocState
	if s == nil {
		return new(stackAllocState)
	}
	if s.f != nil {
		f.fe.Fatalf(src.NoXPos, "newStackAllocState called without previous free")
	}
	return s
}

func putStackAllocState(s *stackAllocState) {
	for i := range s.values {
		s.values[i] = stackValState{}
	}
	for i := range s.interfere {
		s.interfere[i] = nil
	}
	for i := range s.names {
		s.names[i] = LocalSlot{}
	}
	for i := range s.slots {
		s.slots[i] = 0
	}
	for i := range s.used {
		s.used[i] = false
	}
	s.f.Cache.stackAllocState = s
	s.f = nil
	s.live = nil
	s.nArgSlot, s.nNotNeed, s.nNamedSlot, s.nReuse, s.nAuto, s.nSelfInterfere = 0, 0, 0, 0, 0, 0
}

type stackValState struct {
	typ      *types.Type
	spill    *Value
	needSlot bool
	isArg    bool
}

// stackalloc在堆栈帧中为
// 所有未获得寄存器的值分配存储。
// 返回从块ID到该块末尾的堆栈值的映射。
func stackalloc(f *Func, spillLive [][]ID) [][]ID {
	if f.pass.debug > stackDebug {
		fmt.Println("before stackalloc")
		fmt.Println(f.String())
	}
	s := newStackAllocState(f)
	s.init(f, spillLive)
	defer putStackAllocState(s)

	s.stackalloc()
	if f.pass.stats > 0 {
		f.LogStat("stack_alloc_stats",
			s.nArgSlot, "arg_slots", s.nNotNeed, "slot_not_needed",
			s.nNamedSlot, "named_slots", s.nAuto, "auto_slots",
			s.nReuse, "reused_slots", s.nSelfInterfere, "self_interfering")
	}

	return s.live
}

func (s *stackAllocState) init(f *Func, spillLive [][]ID) {
	s.f = f

	// 初始化值信息。
	if n := f.NumValues(); cap(s.values) >= n {
		s.values = s.values[:n]
	} else {
		s.values = make([]stackValState, n)
	}
	for _, b := range f.Blocks {
		for _, v := range b.Values {
			s.values[v.ID].typ = v.Type
			s.values[v.ID].needSlot = !v.Type.IsMemory() && !v.Type.IsVoid() && !v.Type.IsFlags() && f.getHome(v.ID) == nil && !v.rematerializeable() && !v.OnWasmStack
			s.values[v.ID].isArg = hasAnyArgOp(v)
			if f.pass.debug > stackDebug && s.values[v.ID].needSlot {
				fmt.Printf("%s needs a stack slot\n", v)
			}
			if v.Op == OpStoreReg {
				s.values[v.Args[0].ID].spill = v
			}
		}
	}

	// 为需要插槽的值计算活动度信息。
	s.computeLive(spillLive)

	// 在需要插槽的值之间建立干涉图。
	s.buildInterferenceGraph()
}

func (s *stackAllocState) stackalloc() {
	f := s.f

	// 构建从值到其名称的映射（如果有）。
	// 一个值可能与多个名称关联（例如，在
	// 赋值i=j之后）。这一步任意为每个值选择一个名称。
	if n := f.NumValues(); cap(s.names) >= n {
		s.names = s.names[:n]
	} else {
		s.names = make([]LocalSlot, n)
	}
	names := s.names
	empty := LocalSlot{}
	for _, name := range f.Names {
		// 注意：不是上面的“范围f.namedvalue”，因为这是不确定的。
		for _, v := range f.NamedValues[*name] {
			if v.Op == OpArgIntReg || v.Op == OpArgFloatReg {
				aux := v.Aux.(*AuxNameOffset)
				// 永远不要让一个arg绑定到一个不同名称的东西上。
				if name.N != aux.Name || name.Off != aux.Offset {
					if f.pass.debug > stackDebug {
						fmt.Printf("stackalloc register arg %s skipping name %s\n", v, name)
					}
					continue
				}
			} else if name.N.Class == ir.PPARAM && v.Op != OpArg {
				// PPARAM仅绑定到OpArg 
				if f.pass.debug > stackDebug {
					fmt.Printf("stackalloc PPARAM name %s skipping non-Arg %s\n", name, v)
				}
				continue
			}

			if names[v.ID] == empty {
				if f.pass.debug > stackDebug {
					fmt.Printf("stackalloc value %s to name %s\n", v, *name)
				}
				names[v.ID] = *name
			}
		}
	}

	// 将参数分配到其指定的位置。
	for _, v := range f.Entry.Values {
		if !hasAnyArgOp(v) {
			continue
		}
		if v.Aux == nil {
			f.Fatalf("%s has nil Aux\n", v.LongString())
		}
		if v.Op == OpArg {
			loc := LocalSlot{N: v.Aux.(*ir.Name), Type: v.Type, Off: v.AuxInt}
			if f.pass.debug > stackDebug {
				fmt.Printf("stackalloc OpArg %s to %s\n", v, loc)
			}
			f.setHome(v, loc)
			continue
		}
		// 你可能认为下面这个想法是正确的，但你错了。
		// 它几乎可以工作；截至105a6e9518-2021-04-23，
		// GOSSAHASH=11011011001011111==cmd/compile/internal/noder。（*点头）。嵌入式
		// 编译错误。我相信原因是SSA注册
		// 注册分配器解开的谜题之一；如果寄存器
		// 参数最终没有绑定到一个名称，“修复”它是一个坏主意。
		// 
		// if f.DebugTest{
		// if v.Op==OpArgIntReg | | v.Op==OpArgFloatReg{
		// aux:=v.aux（*auxnamefset）
		// loc LocalSlot{N:aux.Name，Type:v.Type，Offset}
		// if f.pass。debug>stackDebug{
		// fmt.Printf（“stackalloc Op%s%s to%s\n”，v.Op，v，loc）
		// }
		// names[v.ID]=loc 
		// continue 
		// }
		// }

	}

	// /对于每种类型，我们都会跟踪我们为该类型分配的所有堆栈插槽。
	// TODO:在等效类型之间共享插槽。我们需要
	// 只在具有相同GC签名的类型之间共享。参见
	// 类型。下面的呼吁同样重要。
	locations := map[*types.Type][]LocalSlot{}

	// 每次我们将一个堆栈槽分配给一个值v时，我们都会记得
	// 我们通过一个位置索引使用的槽[v.Type]。
	slots := s.slots
	if n := f.NumValues(); cap(slots) >= n {
		slots = slots[:n]
	} else {
		slots = make([]int, n)
		s.slots = slots
	}
	for i := range slots {
		slots[i] = -1
	}

	// 为每个需要的值选择一个堆栈插槽。
	var used []bool
	if n := f.NumValues(); cap(s.used) >= n {
		used = s.used[:n]
	} else {
		used = make([]bool, n)
		s.used = used
	}
	for _, b := range f.Blocks {
		for _, v := range b.Values {
			if !s.values[v.ID].needSlot {
				s.nNotNeed++
				continue
			}
			if hasAnyArgOp(v) {
				s.nArgSlot++
				continue // 已经选择了
			}

			// 如果这是一个命名值，请尝试使用名称
			// 泄漏位置。
			var name LocalSlot
			if v.Op == OpStoreReg {
				name = names[v.Args[0].ID]
			} else {
				name = names[v.ID]
			}
			if name.N != nil && v.Type.Compare(name.Type) == types.CMPeq {
				for _, id := range s.interfere[v.ID] {
					h := f.getHome(id)
					if h != nil && h.(LocalSlot).N == name.N && h.(LocalSlot).Off == name.Off {
						// 变量可能会干扰自身。
						// 这很少见，但也有可能发生。
						s.nSelfInterfere++
						goto noname
					}
				}
				if f.pass.debug > stackDebug {
					fmt.Printf("stackalloc %s to %s\n", v, name)
				}
				s.nNamedSlot++
				f.setHome(v, name)
				continue
			}

		noname:
			// 我们可以重用的堆栈插槽集。
			locs := locations[v.Type]
			// 标记干扰值使用的LOC中的所有位置。
			for i := 0; i < len(locs); i++ {
				used[i] = false
			}
			for _, xid := range s.interfere[v.ID] {
				slot := slots[xid]
				if slot >= 0 {
					used[slot] = true
				}
			}
			// 查找未使用的堆栈插槽。
			var i int
			for i = 0; i < len(locs); i++ {
				if !used[i] {
					s.nReuse++
					break
				}
			}
			// 如果没有未使用的堆栈插槽，请分配一个新的。
			if i == len(locs) {
				s.nAuto++
				locs = append(locs, LocalSlot{N: f.fe.Auto(v.Pos, v.Type), Type: v.Type, Off: 0})
				locations[v.Type] = locs
			}
			// 将该索引处的堆栈变量用于v。
			loc := locs[i]
			if f.pass.debug > stackDebug {
				fmt.Printf("stackalloc %s to %s\n", v, loc)
			}
			f.setHome(v, loc)
			slots[v.ID] = i
		}
	}
}

// computeLive计算从块ID到
// 堆栈插槽列表的映射，该堆栈插槽需要在该块末尾使用值ID。
// TODO:如果许多变量位于许多
// 基本块之间，则这可能是二次的。找出一种方法，使这个函数（或者更准确地说，这个函数的用户
// ）只需要线性大小和时间。
func (s *stackAllocState) computeLive(spillLive [][]ID) {
	s.live = make([][]ID, s.f.NumBlocks())
	var phis []*Value
	live := s.f.newSparseSet(s.f.NumValues())
	defer s.f.retSparseSet(live)
	t := s.f.newSparseSet(s.f.NumValues())
	defer s.f.retSparseSet(t)

	// 不要迭代f.块，而是迭代它们的后序。
	// 活性信息向后流动，因此从末尾开始
	// 增加了我们快速稳定的可能性。
	po := s.f.postorder()
	for {
		changed := false
		for _, b := range po {
			// 从块末尾的已知活动值开始
			live.clear()
			live.addAll(s.live[b.ID])

			// 向后传播到块的开头
			phis = phis[:0]
			for i := len(b.Values) - 1; i >= 0; i-- {
				v := b.Values[i]
				live.remove(v.ID)
				if v.Op == OpPhi {
					// 保存phi以备将来使用。
					// 注意：尽管phi本身不需要堆栈插槽，但它的参数可能需要堆栈插槽。所以不要使用needSlot。
					if !v.Type.IsMemory() && !v.Type.IsVoid() {
						phis = append(phis, v)
					}
					continue
				}
				for _, a := range v.Args {
					if s.values[a.ID].needSlot {
						live.add(a.ID)
					}
				}
			}

			// 对于b的每个前一个，扩展其在结束时有效的值列表
			// 不变量：s包含在b开始时有效的值（不包括phi输入）
			for i, e := range b.Preds {
				p := e.b
				t.clear()
				t.addAll(s.live[p.ID])
				t.addAll(live.contents())
				t.addAll(spillLive[p.ID])
				for _, v := range phis {
					a := v.Args[i]
					if s.values[a.ID].needSlot {
						t.add(a.ID)
					}
					if spill := s.values[a.ID].spill; spill != nil {
						// TODO:删除？被使用了吗？
						t.add(spill.ID)
					}
				}
				if t.size() == len(s.live[p.ID]) {
					continue
				}
				// grow p的活动集
				s.live[p.ID] = append(s.live[p.ID][:0], t.contents()...)
				changed = true
			}
		}

		if !changed {
			break
		}
	}
	if s.f.pass.debug > stackDebug {
		for _, b := range s.f.Blocks {
			fmt.Printf("stacklive %s %v\n", b, s.live[b.ID])
		}
	}
}

func (f *Func) getHome(vid ID) Location {
	if int(vid) >= len(f.RegAlloc) {
		return nil
	}
	return f.RegAlloc[vid]
}

func (f *Func) setHome(v *Value, loc Location) {
	for v.ID >= ID(len(f.RegAlloc)) {
		f.RegAlloc = append(f.RegAlloc, nil)
	}
	f.RegAlloc[v.ID] = loc
}

func (s *stackAllocState) buildInterferenceGraph() {
	f := s.f
	if n := f.NumValues(); cap(s.interfere) >= n {
		s.interfere = s.interfere[:n]
	} else {
		s.interfere = make([][]ID, n)
	}
	live := f.newSparseSet(f.NumValues())
	defer f.retSparseSet(live)
	for _, b := range f.Blocks {
		// 将活动性向后传播到块的开头。
		// 如果一个值被定义，而另一个值处于活动状态，则两个值会相互干扰。
		live.clear()
		live.addAll(s.live[b.ID])
		for i := len(b.Values) - 1; i >= 0; i-- {
			v := b.Values[i]
			if s.values[v.ID].needSlot {
				live.remove(v.ID)
				for _, id := range live.contents() {
					// 注意：args可以有不同的类型，但仍然会干扰
					// （彼此或其他值）。见第23522期。
					if s.values[v.ID].typ.Compare(s.values[id].typ) == types.CMPeq || hasAnyArgOp(v) || s.values[id].isArg {
						s.interfere[v.ID] = append(s.interfere[v.ID], id)
						s.interfere[id] = append(s.interfere[id], v.ID)
					}
				}
			}
			for _, a := range v.Args {
				if s.values[a.ID].needSlot {
					live.add(a.ID)
				}
			}
			if hasAnyArgOp(v) && s.values[v.ID].needSlot {
				// OpArg是一个预先溢出的输入参数。
				// 我们在这里重新添加v.ID，因为我们希望这个值在这一点之前就显示为活动。处于活动状态
				// 一直到入口块的开头，都会阻止其他
				// 值被分配到同一个插槽，并在我们有机会加载它之前对
				// 输入值进行重击。

				// TODO（寄存器args）寄存器args显然没有错——有必要吗？
				live.add(v.ID)
			}
		}
	}
	if f.pass.debug > stackDebug {
		for vid, i := range s.interfere {
			if len(i) > 0 {
				fmt.Printf("v%d interferes with", vid)
				for _, x := range i {
					fmt.Printf(" v%d", x)
				}
				fmt.Println()
			}
		}
	}
}

func hasAnyArgOp(v *Value) bool {
	return v.Op == OpArg || v.Op == OpArgIntReg || v.Op == OpArgFloatReg
}
